package learn.link;

import learn.CommUtil;

import java.util.Arrays;
import java.util.HashMap;

/**
 * 将单向链表按某值划分成左边小、中间相等、右边大的形式
 * 1）把链表放入数组里，在数组上做partition（笔试用）
 * 2）分成小、中、大三部分，再把各个部分之间串起来（面试用）
 */
public class SmallerEqualBigger {
    public static void main(String[] args) {
        Node head1 = new Node(7);
        head1.next = new Node(9);
        head1.next.next = new Node(1);
        head1.next.next.next = new Node(8);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(2);
        head1.next.next.next.next.next.next = new Node(5);
        printLinkedList(head1);
        head1 = process1(head1, 5);
        printLinkedList(head1);

    }

    /**
     * 时间复杂度:O(n)
     * 空间复杂度:O(1)
     * 思路:
     * 1.根据pivot把链表分成3个链表,分别是 [<],[=],[>]
     * 2.[<]的尾节点连接[=]的头节点,[=]的尾节点连接[>]的头节点
     */
    public static Node process1(Node head, int pivot) {
        Node sh = null;//[<] 的头节点
        Node st = null;//[<] 的尾节点
        Node eh = null;//[=] 的头节点
        Node et = null;//[=] 的尾节点
        Node mh = null;//[>] 的头节点
        Node mt = null;//[>] 的尾节点
        Node node = head;

        while (node != null) {
            Node next = node.next;
            node.next = null;
            if (node.value < pivot) {
                if (sh == null) {
                    sh = node;
                    st = node;
                } else {
                    st.next = node;
                    st = node;
                }
            } else if (node.value == pivot) {
                if (eh == null) {
                    eh = node;
                    et = node;
                } else {
                    et.next = node;
                    et = node;
                }
            } else {
                if (mh == null) {
                    mh = node;
                    mt = node;
                } else {
                    mt.next = node;
                    mt = node;
                }
            }
            node = next;
        }

        if (st != null) {
            st.next = eh;
            //下一步谁去连[>]头节点
            eh = eh == null ? st : et;
        }

        if (et != null) {
            et.next = mh;
        }

        return (sh != null) ? sh : (eh != null ? eh : mh);
    }

    /**
     * 笨办法:
     * 时间复杂度:O(n)
     * 空间复杂度:O(n)
     * 1.链表插入数组
     * 2.做分区([>] [=] [<])
     * 3.返回arr[0]
     *
     * @param head
     * @param pivot
     * @return
     */
    public static Node process(Node head, int pivot) {
        int size = 0;
        Node node = head;
        while (node != null) {
            size++;
            node = node.next;
        }
        Node[] arr = new Node[size];
        int i = 0;
        node = head;
        while (node != null) {
            arr[i++] = node;
            node = node.next;
        }
        arrPartition(arr, pivot);

        int j = 0;
        for (; j < arr.length - 1; ) {
            arr[j].next = arr[++j];
        }
        arr[j].next = null;
        return arr[0];
    }

    public static void arrPartition(Node[] arr, int pivot) {

        int i = 0;
        int left = -1;
        int right = arr.length;

        while (i < right) {
            if (arr[i].value < pivot) {
                swap(arr, i++, ++left);
            } else if (arr[i].value == pivot) {
                i++;
            } else {
                swap(arr, i, --right);
            }
        }


    }

    public static void swap(Node[] nodeArr, int a, int b) {
        Node tmp = nodeArr[a];
        nodeArr[a] = nodeArr[b];
        nodeArr[b] = tmp;
    }

    public static void printLinkedList(Node node) {
        System.out.println();
        System.out.print("Linked List: ");
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.next;
        }
        System.out.println();
    }

}
